package offer;

public class Solution14 {
    public int cuttingRope(int n) {
        final int MOD = (int) 1e9 + 7;
        if (n <= 4) {
            if (n == 1 || n == 4) {
                return n;
            } else {
                return n - 1;
            }
        }
        long res = 1;
        while (n > 4) {
            res = res * 3 % MOD;
            n -= 3;
        }
        res = res * n % MOD;
        return (int) res;
    }
}
